1. Technical Field
The invention relates to the technical field of path optimization mechanisms. More specifically, the invention relates to aspects in context with a graph based approach for efficiently finding one or more solution paths between two states representative of physical sites or conditions of a physical entity.
2. Background Information
Data that can be represented in the form of a graph is processed in a variety of different contexts. As an example the generation of transportation models for computer-implemented processing tasks such as transportation path optimization can be mentioned.
Such transportation models help to solve problems relating to the transportation of tangible and intangible objects. Tangible objects such as fluids have to be transported via complex pipeline systems. Goods such as construction material require a transportation between remote geographical places across a network of ground, air and sea ways. Intangible objects like electrical signals have to be transported for example within the highly complex wiring system in an airplane. Other intangible objects such as information in the form of electronic mails is sent across the World Wide Web via a plurality of intermediary routers.
Due to their complexity, transportation problems are conventionally modeled and solved on computers using a graph-based approach. In computer science, a graph is an abstract data model that consists of vertices (also called nodes or, in the present context, states) connected via edges. The basic data model for transportation problems includes states in form of locations and zones (as vertices) and connecting transitions in form of lanes (as edges). A transition E=(X, Y) is a (directed or not directed) link between a first state X and a second state Y. A sequence E1, . . . ,En of connected transitions constitutes a path within the graph.
Transportation paths have to be planned taking into account prevailing transportation constraints. Besides the availability of transportation links, transportation hubs, etc., capacity constraints like number of vehicles, network bandwidth, pipeline diameter, etc. can play a role. Additionally, transportation assignments associating transportation means and transportation service providers (e.g. network service providers) exist. Basing the transportation paths determination, inter alia, on such transportation assignments aims at saving resources (such as the number of intermediary components involved in a particular transportation task, etc.).
When implemented in a computer system, the conventional data models for transportation optimization are not under all circumstances satisfactory. The transportation optimization is often carried out either solely on a detailed level or first on an aggregated and afterwards on a detailed level. Nevertheless, the transportation master data is often not structured to allow for a fast and smooth processing. In addition to master data on either aggregated level (utilized mainly to save memory consumption) or detailed level (utilized mainly to be precise or to state exceptions), one might think of defining master data striking several levels. In such a case the data would not need to be converted by the application before it can start the transportation optimization. This pre-processing step is, however, technically disadvantageous if the actual optimization is on average not comprehensive and/or the single requests for transportation paths cannot be gathered over a longer period of time (e.g., in a real-time environment). On the other hand, the conversion step may further complicate maintenance, as the optimization data does not directly reflect the master data on the database.
Accordingly, there is a need for a more flexible transportation optimization approach that can easily be implemented on multi-tiered (or other) computer systems and that does not unnecessarily consume processing and memory resources.